package com.qjc.demo.train.strmatch;

/**
 * @ClassName: RKMatch
 * @Description: 字符串匹配算法- Rabin-Karp 算法
 * 我们通过哈希算法对主串中的 n-m+1 个子串分别求哈希值，然后逐个与模式
 * 串的哈希值比较大小。如果某个子串的哈希值与模式串相等，那就说明对应的子串和模式串匹配了（这
 * 里先不考虑哈希冲突的问题）。因为哈希值是一个数字，数字之间比较是否相等是非常快速的，所以模
 * 式串和子串比较的效率就提高了
 * @Author: qjc
 * @Date: 2022/5/2 4:17 PM
 */
public class RKMatch {

    /**
     * RK 算法的的时间复杂度为O(m+n)
     * m:为匹配串长度
     * n:为主串长度
     * 应用
     * 适用于匹配串类型不多的情况，比如：字母、数字或字母加数字的组合 62 (大小写字母+数字)
     */
    public static boolean isMatch(String main, String sub) {
        int subHash = strToHash(sub);
        for (int i = 0; i <= (main.length() - sub.length()); i++) {
            if (subHash == strToHash(main.substring(i, i + sub.length()))) {
                return true;
            }
        }
        return false;
    }

    /**
     * 支持 a-z 二十六进制
     * 获得字符串的hash值
     */
    private static int strToHash(String src) {
        int hash = 0;
        for (int i = 0; i < src.length(); i++) {
            hash *= 26;
            hash += (src.charAt(i) - 97);
        }
        return hash;
    }

    public static void main(String[] args) {
        System.out.println(isMatch("sdfrtetcnbccsd", "tet"));
    }


}
